# 最长递增子序列: https://leetcode-cn.com/problems/longest-increasing-subsequence/

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        """ 
            动态规划， 这点不好想，正常逻辑都是求当前节点 往后的子序列有多长， 但是这里是反着。
            求到当前节点的 最大子序列长度。 求出每个节点的最大子序列长度。
        """
        dp = [1] * len(nums)
        # 记录最大结果
        rst = 0
        for i in range(len(nums)):
            max_sequence = 0
            for j in range(0, i):
                if dp[j] > max_sequence and nums[j] < nums[i]:
                    max_sequence = dp[j]
            dp[i] = max_sequence + 1
            rst = max(dp[i], rst)
        
        return rst


# 还可以改一下。 不用直接初始化 dp为 len(nums) 长
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        """ 
            动态规划， 这点不好想，正常逻辑都是求当前节点 往后的子序列有多长， 但是这里是反着。
            求到当前节点的 最大子序列长度。 求出每个节点的最大子序列长度。
        """
        dp = []
        # 记录最大结果
        rst = 0
        for i in range(len(nums)):
            max_sequence = 0
            for j in range(0, i):
                if dp[j] > max_sequence and nums[j] < nums[i]:
                    max_sequence = dp[j]
            dp.append(max_sequence + 1)
            rst = max(dp[i], rst)
        
        return rst